"""
首先，想到的应该是暴力算法
其次，需要存储某个元素时我们试着想一下是不是可以用栈，如果和顺序相关可以用单调栈
"""
# 暴力算法
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        GElist = []
        for v1 in nums1:
            flag = False
            for v2 in nums2:
                if v1 == v2:
                    flag = True
                if flag and v2 > v1:
                    GElist.append(v2)
                    break
            else:
                GElist.append(-1)
        return GElist

# 用栈实现动态规划
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        nGEdic = {}
        nGElist = []
        for v1 in nums2:
            while len(stack) != 0 and v1 > stack[-1]:
                tmp = stack.pop()
                nGEdic[tmp] = v1
            stack.append(v1)
        for v2 in nums1:
           nGElist.append(nGEdic[v2] if v2 in nGEdic.keys() else -1)
        return nGElist